package com.wtgroup.demo.mianshi.算法.排序;

/**
 * 区分堆size, 和堆数组. 堆size<=数组长度
 *
 * 广度优先排列的数组完全数组二叉树, len/2-1 刚好就是最后一个父节点.
 *
 * @see [数据结构与算法分析]
 * @author Nisus
 * @version 0.1
 * @date 2019/9/14 18:05
 */
public class HeapSort implements ComparableSort {

    public static void sort(Comparable[] arr) {
        // 建立堆
        for (int i = arr.length / 2 - 1; i >=0 ; i--) {
            percolateDown(arr, i, arr.length);
        }

        // 删除堆顶, 直到删完
        for (int i = arr.length; i>0; i--) {
            deleteTop(arr, i);
        }

    }

    /**下滤
     *
     * 实现"堆化".
     * "堆化": 堆有序化. 每个小堆局部堆化, 但需要继续考虑其子堆的"堆化". 每个局部堆化, 可能会破坏父或子的有序.
     * 堆化, 会递归照顾子堆的有序性, 故, 自底向上, 可整个堆有序.
     *
     * 大顶堆下, 每个局部堆中, 小值都会往下滤, 大的往上浮.
     * @param arr 源数组
     * @param start 下滤的起始节点
     * @param size 堆规模
     */
    private static void percolateDown(Comparable[] arr, int start, int size) {
        Comparable tmp = arr[start];
        // 如果当前节点就是父子中最大者, 直接结束了, 无需下滤.
        int child;
        int i = start;
        for ( ; (child=leftChild(i))<size; i=child) { // 有左孩子, 即非叶子节点
            // 最大的孩子往上移过来
            // 有右孩子, 且右孩子更大
            if (child + 1 < size && arr[child].compareTo(arr[child + 1]) < 0) {
                child++;
            }
            if (tmp.compareTo(arr[child]) < 0) {
                // 最大的孩子换到当前节点, 最大孩子位置变成空节点, 作为下一轮下滤的起始
                arr[i] = arr[child];
            }else{
                break; // 结束下滤
            }
        }
        arr[i] = tmp;
    }

    private static int leftChild(int i) {
        return 2*i+1;
    }

    /**"删除"堆顶元素.
     * @return 堆顶值
     */
    public static Comparable deleteTop(Comparable[] arr, int size) {
        // 堆顶节点和堆尾节点交换
        // 下滤, 保持堆序
        // 堆规模缩小 1
        // 堆数组尾部备份的是删除的节点, 当堆"删除"完毕后, 留下的数组就是有序的
        Comparable top = arr[0];
        Comparable tmp = arr[size-1];
        arr[size - 1] = top;
        arr[0] = tmp;

        percolateDown(arr, 0, size-1); // 堆规模缩小1个

        return top;
    }

}
